def linear_search(arr, target):
    """
    线性查找算法
    ：param arr: 待查找的列表
    ：param target: 要查找的目标值
    ：return: 目标值的索引，如果不存在则返回-1
    """
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1

data = [4, 2, 7, 1, 9, 5, 3]
target_value = 7


result = linear_search(data, target_value)
print(f"元素 {target_value} 的索引是： {result}" if result != -1 else "元素未找到")

def binary_search(arr, target):
    """
    二分查找算法
    :param arr: 已排序的列表
    :param target: 要查找的目标值
    :return: 目标值的索引，如果不存在则返回-1
    """
    left, right = 0, len(arr) - 1

    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1


sorted_data = sorted([4, 2, 7, 1, 9, 5, 3])
target_value = 5

result = binary_search(sorted_data, target_value)
print(f"元素 {target_value} 的索引是： {result}" if result != -1 else "元素未找到")

def binary_search_recursive(arr, target,left, right):
    """
    递归实现的二分查找
    :param arr: 已排序的列表
    :param target: 要查找的目标值
    :param left: 当前搜索区间的左边界
    :param right: 当前搜索区间的有边界
    :return: 目标值的索引，如果不存在则返回-1
    """
    if left > right:
        return -1


    mid = (left + right) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search_recursive(arr, target, mid + 1, right)
    else:
        return binary_search_recursive(arr, target, left, mid - 1)


    sorted_data = sorted([4, 2, 7, 1, 9, 5, 3])
    target_value = 3


    result = binary_search_recursive(sorted_data, target_value,0,len(sorted_data) - 1)
    print(f"元素 {target_value} 的索引是： {result}" if result != -1 else" 元素未找到")

    import time


    large_data = list(range(1, 1000001))



    target = 9999999
    start_time = time.time()
    result = linear_search(large_data, target)
    end_time = time.time()
    print(f"线性查找耗时： {end_time - start_time:.6f}秒")



    start_time = time.time()
    result = binary_search(large_data, target)
    end_time = time.time()
    print(f"二分查找耗时： {end_time - start_time:.6f}秒")


















